#include <stdio.h>
#include <memory.h>

static const int MAX_LEN = 100;
int solution[MAX_LEN + 1][MAX_LEN + 1];

int gene1[MAX_LEN + 1];
int gene2[MAX_LEN + 1];

int score[5][5] =
{
	{5, -1, -2, -1, -3},
	{-1, 5, -3, -2, -4},
	{-2, -3, 5, -2, -2},
	{-1, -2, -2, 5, -1},
	{-3, -4, -2, -1},
};

void read(int* gene, int &len)
{
	char str[MAX_LEN];
	scanf ("%d %s", &len, str);
	for (int i = 0; i < len; i++)
	{
		char c = str[i];
		if (c == 'A')
			gene[i] = 0;
		else if (c == 'C')
			gene[i] = 1;
		else if (c == 'G')
			gene[i] = 2;
		else if (c == 'T')
			gene[i] = 3;
	}
}

int main()
{
	int n;
	scanf ("%d", &n);
	while (n--)
	{
		int l1, l2;
		read(gene1, l1);
		read(gene2, l2);

		memset(solution, 0, sizeof(solution));

		for (int i = 1; i <= l1; i++)
		{
			solution[i][0] = solution[i-1][0] + score[gene1[i-1]][4];
		}
		for (int j = 1; j <= l2; j++)
		{
			solution[0][j] = solution[0][j-1] + score[4][gene2[j-1]];
		}

		for (int i = 1; i <= l1; i++)
		{
			for (int j = 1; j <= l2; j++)
			{
				int max = solution[i-1][j-1] + score[gene1[i-1]][gene2[j-1]];
				int temp = solution[i][j-1] + score[4][gene2[j-1]];
				if (temp > max)
					max = temp;
				temp = solution[i-1][j] + score[gene1[i-1]][4];
				if (temp > max)
					max = temp;
				solution[i][j] = max;
			}
		}
		printf ("%d\n", solution[l1][l2]);
	}
}